package com.tgy.algorithm.base._二叉树;


class AVLInfo {
    boolean isAVL;
    int height;
    AVLInfo(int height, boolean isAVL) {
        this.height = height;
        this.isAVL = isAVL;
    }
    AVLInfo(int height) {
        this.height = height;
    }
}

public class _判断二叉树是否是平衡二叉树 {


    public static BiTreeNode generalBiTreeNode() {
        /**
         *              1
         *         2           3
         *       4     5    6
         *                  7
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(4);
        root.left.right = new BiTreeNode(5);
        root.right.left = new BiTreeNode(6);
        root.right.left.left = new BiTreeNode(7);

        return root;
    }



    /*
        判断二叉树是否是平衡二叉树
     */
    public static boolean isAVL(BiTreeNode root) {
        return doIsAVL(root).isAVL;
    }

    public static AVLInfo doIsAVL(BiTreeNode root) {

        if (root == null) {
            return new AVLInfo(0,true);
        }

        AVLInfo leftInfo = doIsAVL(root.left);
        AVLInfo rightInfo = doIsAVL(root.right);
        boolean isAVL = leftInfo.isAVL && rightInfo.isAVL && Math.abs(leftInfo.height - rightInfo.height) <= 1;
        AVLInfo info = new AVLInfo(Math.max(leftInfo.height, rightInfo.height) + 1, isAVL);
        return info;
    }


    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
        System.out.println(isAVL(root));
    }
}
